// https://www.lintcode.com/problem/insert-node-in-a-binary-search-tree/my-submissions
// 85. 在二叉查找树中插入节点

// BST的性质：
// • BST的定义？
// – 左边都比root小，右边都比root大

// • 把BST规范的画出来是什么样子？
// – 向下投影出的序列是从小到大的顺序

// • BST的中根遍历（Inorder 左中右），节点访问顺序是什么样的？
// – 小到大的顺序（中序遍历就是投影顺序）



// 一棵BST定义为：

// 节点的左子树中的值要严格小于该节点的值。
// 节点的右子树中的值要严格大于该节点的值。
// 左右子树也必须是二叉查找树。
// 一个节点的树也是二叉查找树。


/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */


class Solution {
public:
    /*
     * @param root: The root of the binary search tree.
     * @param node: insert this node into the binary search tree
     * @return: The root of the new binary search tree.
     */
     
    // 递归
    // TreeNode * insertNode(TreeNode * root, TreeNode * node) {
    //     if (!root)
    //     {
    //         return node;
    //     }
    //     if (node->val < root->val)
    //     {
    //         root->left = insertNode(root->left, node);
    //     }
    //     else
    //     {
    //         root->right = insertNode(root->right, node);
    //     }
    //     return root;
    // }
    
    // 非递归
    TreeNode * insertNode(TreeNode * root, TreeNode * node) {
        TreeNode * pre;
        TreeNode * cur = root;
        if (!root)
        {
            return node;
        }
        while (cur)
        {
            pre = cur;
            if (node->val < cur->val)
            {
                cur = cur->left;
            }
            else
            {
                cur = cur->right;
            }
        }
        if (pre && node->val < pre->val)
        {
            pre->left = node;
        }
        else if (pre)
        {
            pre->right = node;
        }
        return root;
    }
};